/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/unique-paths
   @Language: C++
   @Datetime: 16-02-09 05:22
   */

// Method 1, DP, Space O(m*n), Time O(m*n), 80ms
class Solution {
public:
	/**
	 * @param n, m: positive integer (1 <= n ,m <= 100)
	 * @return an integer
	 * Tip : To reach F[i][j], there are two prev node:
	 *       F[i-1][j] and F[i][j-1]
	 */
	int uniquePaths(int m, int n) {
		// wirte your code here
		int F[101][101], i, j;
		for(i=0; i<m; F[i++][0]=1);
		for(j=0; j<n; F[0][j++]=1);
		for(i=1; i<m; ++i)
			for(j=1; j<n;++j)
				F[i][j]=F[i][j-1]+F[i-1][j];
		return (m && n) ? F[m-1][n-1] : 0;
	}
};

// Method 2, DP with slide window, Space O(m+n), Time O(m*n), 74ms
class Solution {
public:
	/**
	 * @param n, m: positive integer (1 <= n ,m <= 100)
	 * @return an integer
	 */
	int uniquePaths(int m, int n) {
		// wirte your code here
		int Rows[101], Cols[101], i, j;
		for(i=0; i<m; Rows[i++]=1);
		for(j=0; j<n; Cols[j++]=1);
		for(i=1; i<m; ++i)
			for(j=1; j<n;++j)
				Rows[i] = Cols[j] = Cols[j]+Rows[i];
		return (m && n) ? Rows[m-1] : 0;
	}
};

// Method 3, Math Combination, C(m+n-2,min(m,n)-1), Time O(min(m,n))
class Solution {
public:
	/**
	 * @param n, m: positive integer (1 <= n ,m <= 100)
	 * @return an integer
	 */
	int uniquePaths(int m, int n) {
		// wirte your code here
		if (!m || !n) return 0; // C(m+n-2,min(m,n)-1)
		long k=min(m,n)-1, c=1, i=1;
		for (n+=m-2; i<=k; c=c*(n--)/(i++));
		return c;
	}
};
